structure constantprop :
sig 				
    val propogateconstants : Tree.stm list * Reachingdefs.rdgraph-> Tree.stm list   
end =

struct 

    structure E = ErrorMsg
    structure RD = Reachingdefs
    structure GB = Graph.Table
    structure M = Temp
    structure R=  Tree
    structure MB = M.Table    
    structure OPT = Option
    structure VEC = Vector
    structure ARR = Array
    structure BITS = BitArray 

(* ins - array of bitarrys- contains all incoming reaching defs for the node
   out- array o bitarrays contains all outgoing reaching defs for the node
   def- table temp-> node list, contains for the temp nodes where this temp is defined
   nodestm - table node-> stm, contains for every node the number of the statement, correspondence between node and statement	
   use - a table   temp -> node list, for every temp contains the list of nodes where this temp is used  
*)
   
 
 fun propogateconstants (stms, RD.RDGRAPH {ins=	ins,out=out,defs=defs,nodestm, use, nodes, nodetable=nodetable}) = 
     let 
     	 val n= ref 0
         val nodeCount= length(nodes)        
	 val newstms= ref stms

         fun definionreached (defnodeindex, usenode, t)=
		      let val  reached= ref false
		      	  val  reached1= ref false
			  val  reached2= ref false
 			  fun  nodeIndex n = OPT.getOpt (GB.look (nodetable, n), ~1)
			  fun  getindices []=[] 
			  | getindices(hd::tail)= let val ndindex= nodeIndex hd
			    			      		 in  if (ndindex=defnodeindex) then getindices(tail) else ndindex :: getindices(tail)
								 end			       
			  val  usenodeindex=nodeIndex  usenode 
			  val  temp  =   BITS.bits (nodeCount, [defnodeindex]) 
		      	  val  rds=ARR.sub (ins, usenodeindex)  (*find reaching definitons of the USE node- bit array*)
			  val  tds=OPT.getOpt(MB.look(defs,t),[]) (*find nodes- all  definitons of the temoporary t*)	
			  val temp1=getindices tds (*list of nodeindices- definitions of t, but not including defnodeindex- all other definitions of t*)
			  val temp2= BITS.bits (nodeCount, temp1) (*bitarray of all definitions of t excluding defnodeindex*)		  
		      in
			( (*if defnodeindex is in rds and no other nodes of tds are in rds then definion is reached*)

	         	 (*checking whether  defnodeindex is in the rds*)
			 if BITS.isZero (BITS.andb (rds, temp, nodeCount)) then () else reached1:=true

			(*checking whether  any other tds are not in rds*)
			; if BITS.isZero (BITS.andb (rds, temp2, nodeCount)) then reached2:=true else ()
			; if !reached1 andalso !reached2 then reached:= true  else ()
			;!reached
			)
		      end

           fun modifystatement (node,t,i)= (*function modifies statement by substituting a temp with the constant*)
		    	let  val stmnum=OPT.getOpt(GB.look(nodestm,node),0)
			     val oldstm= List.nth (!newstms,stmnum)
			     val newstm= ref oldstm		
		        in
			     ( (case oldstm of 
			      R.MOVE (e1 ,e2) => newstm:=R.MOVE (e1,i)
			     | R.CJUMP (rop,e5,e6,l1,l2) =>( case e5 of t => newstm := R.CJUMP (rop, i, e6, l1,l2);
							     case e6 of t => newstm := R.CJUMP (rop, e5, i, l1,l2)
							   )
			     | R.JUMP (e,ls) => newstm := R.JUMP (i,ls)
			     |_ => ()
			     )
			     ;newstms := List.take( !newstms,stmnum ) @ [!newstm] @ List.drop (!newstms, (stmnum+1))
			     )
			end
				
     in
	(while (!n < nodeCount)  do (
	      let val node=List.nth(nodes,!n)
	      	  val stmnumber=OPT.getOpt(GB.look(nodestm,node),0)
         	  val defstm=List.nth(stms,stmnumber)   

	      in
		  (case defstm of
		  R.MOVE (R.TEMP t, R.CONST i) => (let val uses=OPT.getOpt(MB.look(use,t),[]) (*find all nodes which uses the temporary t*)	       	   
						   in
							app (fn use=> if definionreached(!n,use,t) then modifystatement(use,t,R.CONST i) else ()) uses	(*if definition is reached modify*)      
		       				   end)
		  | _ => ())		              
	      end
              ;n := !n + 1
              ) 	
	      ; !newstms
        )     				
     end (*1st outer let end*)
end (*structure end*)
